package Kadane算法;

/**
 * 53. 最大子数组和
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 子数组是数组中的一个连续部分。
 *
 * 核心思路：Kadane算法（动态规划）
 * 1: 核心观察：
 *  对于每个元素，有两种选择：
 *      将其加入当前子数组；
 *      以该元素作为新子数组的起点；目标是选择使得当前子数组和最大值的方式。
 *  2：动态维护变量：
 *      currentMax: 记录以当前元素结尾的子数组的最大和；
 *      maxSum ： 记录全局最大子数组之和
 *  3：递推关系：
 *      每一步更新 currentMax = max(currentMax + nums[i], nums[i]);
 *      更新全局最大值：maxSum = max(maxSum, currentMax);
 *
 */
public class L_53 {
    public int maxSubArray(int[] nums) {
        // 初始化变量
        int currentMax = nums[0];
        int maxSum = nums[0];
        // 从i = 1 开始进行动态规划
        for (int i = 1; i < nums.length; i++) {
            // 决定是否将当前元素加入当前子数组，或者以当前元素作为新子数组的起点
            // 如果 currentMax 是负数，则当前元素单独作为新子数组会更优
            // 如果当前元素加上之前的最大值大于当前元素，则当前最大值等于之前的最大值加上当前元素；否则当前最大值等于当前元素，以当前元素重新为起点累加
            currentMax = Math.max(nums[i], currentMax + nums[i]);
            // 更新全局最大值
            maxSum = Math.max(maxSum, currentMax);
        }
        return maxSum;
    }
}
